#ifndef TOPO_H_
#define TOPO_H_

#include <algorithm>
#include <vector>

namespace lxj
{
// 最大食物链计数
// a -> b，代表a在食物链中被b捕食
// 给定一个有向无环图，返回
// 这个图中从最初级动物到最顶级捕食者的食物链有几条
// 测试链接 : https://www.luogu.com.cn/problem/P4017
class FoodLines {
    inline constexpr static int MAXN = 5001, MAXM = 500001;
    inline constexpr static int MOD = 80112002;

    // 链式前向星
    inline static int head[MAXN] = {};
    inline static int next[MAXM] = {};
    inline static int to[MAXM]   = {};
    inline static int cnt        = 0;

    // 队列
    inline static int queue[MAXN] = {};

    // 入度表
    inline static int indegree[MAXN] = {};

    // 拓扑排序需要的推送信息
    inline static int lines[MAXN] = {};

    inline static int n = 0, m = 0;

    inline void build()
    {
        std::fill(head, head + n + 1, 0);
        std::fill(indegree, indegree + n + 1, 0);
        std::fill(lines, lines + n + 1, 0);
    }

    inline void addEdge(int u, int v)
    {
        next[cnt] = head[u];
        to[cnt]   = v;
        head[u]   = cnt++;
    }

public:
    inline int ways(int num, const std::vector<std::vector<int>>& edges)
    {
        n = num;
        m = edges.size();
        build();
        cnt = 1;
        for (auto& edge : edges) {
            addEdge(edge[0], edge[1]);
            indegree[edge[1]]++;
        }

        int l = 0, r = 0;
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                queue[r++] = i;
                lines[i]   = 1;
            }
        }

        int ans = 0;
        while (l < r) {
            int u = queue[l++];
            if (head[u] == 0) {
                ans = (ans + lines[u]) % MOD;
            }
            else {
                for (int ei = head[u]; ei != 0; ei = next[ei]) {
                    int v    = to[ei];
                    lines[v] = (lines[v] + lines[u]) % MOD;
                    if (--indegree[to[ei]] == 0) {
                        queue[r++] = to[ei];
                    }
                }
            }
        }
        return ans;
    }
};

// 喧闹和富有
// 从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值
// 给你一个数组richer，其中richer[i] = [ai, bi] 表示
// person ai 比 person bi 更有钱
// 还有一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值
// richer 中所给出的数据 逻辑自洽
// 也就是说，在 person x 比 person y 更有钱的同时，不会出现
// person y 比 person x 更有钱的情况
// 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是,
// 在所有拥有的钱肯定不少于 person x 的人中，
// person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
// 测试链接 : https://leetcode.cn/problems/loud-and-rich/
inline std::vector<int> loudAndRich(std::vector<std::vector<int>>& richer, std::vector<int>& quiet)
{
    int                           n = quiet.size();
    std::vector<std::vector<int>> graph(n, std::vector<int>());
    std::vector<int>              indegree(n);
    for (auto& rich : richer) {
        graph[rich[0]].push_back(rich[1]);
        indegree[rich[1]]++;
    }

    std::vector<int> queue(n);
    int              l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue[r++] = i;
    }

    std::vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = i;
    }

    while (l < r) {
        int cur = queue[l++];
        for (int next : graph[cur]) {
            ans[next] = quiet[ans[cur]] < quiet[ans[next]] ? ans[cur] : ans[next];
            if (--indegree[next] == 0) {
                queue[r++] = next;
            }
        }
    }

    return ans;
}

// 并行课程 III
// 给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n
// 同时给你一个二维整数数组 relations ，
// 其中 relations[j] = [prevCoursej, nextCoursej]
// 表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）
// 同时给你一个下标从 0 开始的整数数组 time
// 其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
// 请你根据以下规则算出完成所有课程所需要的 最少 月份数：
// 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
// 你可以 同时 上 任意门课程 。请你返回完成所有课程所需要的 最少 月份数。
// 注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）
// 测试链接 : https://leetcode.cn/problems/parallel-courses-iii/
inline int minimumTime(int n, std::vector<std::vector<int>>& relations, std::vector<int>& time)
{
    std::vector<std::vector<int>> graph(n + 1, std::vector<int>());
    std::vector<int>              indegree(n + 1);
    for (auto& relation : relations) {
        graph[relation[0]].push_back(relation[1]);
        indegree[relation[1]]++;
    }

    std::vector<int> queue(n);
    int              l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) queue[r++] = i;
    }

    std::vector<int> cost(n + 1);
    int              ans = 0;
    while (l < r) {
        int cur = queue[l++];
        cost[cur] += time[cur - 1];
        ans = std::max(ans, cost[cur]);
        for (int next : graph[cur]) {
            cost[next] = std::max(cost[next], cost[cur]);
            if (--indegree[next] == 0) queue[r++] = next;
        }
    }
    return ans;
}

// 参加会议的最多员工数
// 一个公司准备组织一场会议，邀请名单上有 n 位员工
// 公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工
// 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工
// 每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议
// 每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite
// 其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目
// 测试链接 : https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/
inline int maximumInvitations(std::vector<int>& favorite)
{
    int              n = favorite.size();
    std::vector<int> indegree(n);
    for (auto i : favorite) {
        indegree[i]++;
    }

    std::vector<int> queue(n);
    int              l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue[r++] = i;
    }

    std::vector<int> deep(n);
    while (l < r) {
        int cur    = queue[l++];
        int next   = favorite[cur];
        deep[next] = std::max(deep[next], deep[cur] + 1);
        if (--indegree[next] == 0) queue[r++] = next;
    }

    int sumOfSmallRings = 0, bigRings = 0;
    for (int i = 0; i < n; i++) {
        if (indegree[i] > 0) {
            int ringSize = 1;
            indegree[i]  = 0;
            for (int j = favorite[i]; j != i; j = favorite[j]) {
                ringSize++;
                indegree[j] = 0;
            }
            if (ringSize == 2) {
                sumOfSmallRings += 2 + deep[i] + deep[favorite[i]];
            }
            else {
                bigRings = std::max(bigRings, ringSize);
            }
        }
    }
    return std::max(sumOfSmallRings, bigRings);
}
}   // namespace lxj

#endif